package com.suiwei.advanced.algorithm;

import org.junit.jupiter.api.Test;
import java.util.Arrays;
/**
 * @author suiwei
 * @date 2023/5/8 21:02 数组相关的算法
 */
public class ArrayDemo {
  // 冒泡排序：相邻的两个数做比较，如果第一个比第二个大，那么就交换他们两个，第一次后，最大值放在最大所引处
  @Test
  void bubbleSort() {
    int[] arr = {3, 2, 1, 4};
    // 外循环：比较的轮数
    for (int i = 0; i < arr.length - 1; i++) {
      // 内循环：比较的次数
      // -1：避免索引越界
      // -i：提高效率
      for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
    System.out.println(Arrays.toString(arr));
  }
  // 选择排序：从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较、如果当前元素更大就交换，第一次后，最小的出现在0索引处
  @Test
  void selectSort() {
    int[] arr = {3, 2, 1, 4};
    // 轮数;第一轮确定左侧最小元素，第二轮确定第二个...
    for (int i = 0; i < arr.length - 1; i++) {
      // 第一轮，拿着第一个元素，依次与后面的所有元素比较；第二轮，拿着第二个元素，依次与后面的比较...
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
    }
    System.out.println(Arrays.toString(arr));
  }
  // 找元素在数组中的索引位置
  // 二分查找前提：数组中的数据必须是排好序的
  @Test
  void binarySearch() {
    int[] arr = {11, 22, 33, 44, 55, 66, 77, 88, 99};
    int min = 0;
    int max = arr.length - 1;
    int mid;
    int target = 100;
    while (min <= max) {
      mid = (min + max) / 2;
      if (target > arr[mid]) {
        min = mid + 1;
      } else if (target < arr[mid]) {
        max = mid - 1;
      } else {
        System.out.println(mid);
        // 没有break，就会无限循环
        break;
      }
    }
    System.out.println(-1);
  }
}
